class FARule:
    def __init__(self, state, character, next_state):
        self.state = state
        self.character = character
        self.next_state = next_state

    def applies_to(self, state, character):
        return self.state == state and self.character == character

    def follow(self):
        return self.next_state

    def __repr__(self):
        return f"<FARule {repr(self.state)}--{self.character} -->{repr(self.next_state)}>"


class NFARulebook:
    def __init__(self, rules):
        self.rules = rules

    def rule_for(self, state, character):
        result = []
        for rule in self.rules:
            if rule.applies_to(state, character):
                result.append(rule)

        return result

    def follow_rules_for(self, state, character):
        result = []
        applicable_rules = self.rule_for(state, character)
        for rule in applicable_rules:
            next_state = rule.follow()
            result.append(next_state)
        return result

    def next_states(self, states, character):
        result = set()
        for state in states:
            next_state_list = self.follow_rules_for(state, character)
            for next_state in next_state_list:
                result.add(next_state)
        return result
    
    def follow_free_moves(self, states):
        more_states = self.next_states(states, None)
        if more_states.issubset(states):
            return states
        else:
            return self.follow_free_moves(states.union(more_states))
            
    
    def __repr__(self):
        return f"<struct NFARulebook rules=[...]>"


class NFA:
    def __init__(self, current_states, accept_states, rulebook):
        self._current_states = current_states
        self.accept_states = accept_states
        self.rulebook = rulebook

    def accepting(self):
        accept_states = set(self.accept_states)
        current_states = self.current_states()
        return not current_states.isdisjoint(accept_states)
    
    def read_character(self, character):
        current_states = self.current_states()
        next_states = self.rulebook.next_states(current_states, character)
        self._current_states = next_states
    
    def read_string(self, string):
        for character in string:
            self.read_character(character)

    def current_states(self):
        return self.rulebook.follow_free_moves(self._current_states)

class NFADesign:
    def __init__(self, start_state, accept_states, rulebook):
        self.start_state = start_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def accepts(self, string):
        nfa = self.to_nfa()
        nfa.read_string(string)
        return nfa.accepting()


    def to_nfa(self):
        return NFA(set([self.start_state]),self.accept_states, self.rulebook)

    def __repr__(self):
        return f"<struct NFADesign start_state={self.start_state}, accept_states={self.accept_states}, rulebook={self.rulebook}>"

if __name__ == "__main__":
    # rulebook = NFARulebook(
    # [
    #     FARule(1,'a',1),FARule(1,'b',1),FARule(1,'b',2),
    #     FARule(2,'a',3),FARule(2,'b',3),
    #     FARule(3,'a',4),FARule(3,'b',4),
    # ]
    # )
    # print(rulebook)
    # print(rulebook.next_states(set([1]),'b'))
    # print(rulebook.next_states(set([1,2]),'a'))
    # print(rulebook.next_states(set([1,3]),'b'))


    # 测试NFA的accepting方法 
    # print(NFA(set([1]),[4], rulebook).accepting())
    # print(NFA(set([1,2,4]),[4], rulebook).accepting())

    # 测试NFA
    # nfa = NFA(set([1]),[4], rulebook)
    # print(nfa.accepting())
    # nfa.read_character('b')
    # print(nfa.accepting())
    # nfa.read_character('a')
    # print(nfa.accepting())
    # nfa.read_character('b')
    # print(nfa.accepting())

    # nfa = NFA(set([1]), [4], rulebook)
    # print(nfa.accepting())
    # nfa.read_string('bbbbb')
    # print(nfa.accepting())

    # 测试NFADesign
    # nfa_design = NFADesign(1,[4],rulebook)
    # print(nfa_design)
    # print(nfa_design.accepts('bab'))
    # print(nfa_design.accepts('bbbbb'))
    # print(nfa_design.accepts('bbabb'))

    #测试Free Moves
    rulebook = NFARulebook(
        [
            FARule(1,None,2),
            FARule(1,None,4),
            FARule(2,'a',3),
            FARule(3,'a',2),
            FARule(4,'a',5),
            FARule(5,'a',6),
            FARule(6,'a', 4)
        ]
    )
    # print(rulebook)
    # print(rulebook.next_states(set([1]),None))
    # print(rulebook.follow_free_moves(set([1])))

    nfa_design = NFADesign(1, [2, 4], rulebook)
    # print(nfa_design)
    # print(nfa_design.accepts('aa'))
    # print(nfa_design.accepts('aaa'))
    # print(nfa_design.accepts('aaaaa'))
    # print(nfa_design.accepts('aaaaaa'))

